package com.wfm.leetcode.editor.cn;

import com.wfm.common.TreeNode;
import java.util.HashMap;

/**
 * map为key：int[],  int[]有两个元素，
 * int[0]代表选key，int[1]代表不选key
 */
public class PThree37打家劫舍III{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int rob(TreeNode root) {
        HashMap<TreeNode,int[]> m = new HashMap<>();
        dfs(root,m);
        int[] ints = m.get(root);
        return Math.max(ints[0],ints[1]);
    }
    void dfs(TreeNode root, HashMap<TreeNode,int[]> m){
        if(root==null) return;
        dfs(root.left,m);
        dfs(root.right,m);
        if(root.left==null&&root.right==null){
            m.put(root,new int[]{root.val,0});
        }else if(root.left==null){
            int[] r = m.get(root.right);
            m.put(root,new int[]{root.val+r[1],Math.max(r[0],r[1])});
        }else if(root.right==null){
            int[] l = m.get(root.left);
            m.put(root,new int[]{root.val+l[1],Math.max(l[0],l[1])});
        }else {
            int[] l = m.get(root.left);
            int[] r = m.get(root.right);
            int selectRoot = root.val+l[1]+r[1];
            int noSelectRoot = Math.max(l[0],l[1])+Math.max(r[0],r[1]);
            m.put(root,new int[]{selectRoot,noSelectRoot});
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new PThree37打家劫舍III().new Solution();
        TreeNode treeNode = TreeNode.generatorTreeNode("3,2,3,null,3,null,1");
        int rob = solution.rob(treeNode);
        System.out.println(rob);
    }
}